#include<string>
#include<array>
using namespace std;
class Solution {
public:
//保存所有子串是否回文 i j
//dp[i][j]=dp[i+1][j-1]
    int countSubstrings(string s) {
        array<array<bool,1000>,1000>dp;
        for(auto &e:dp)e.fill(false);
        int ans=0;
        //注意填表顺序 用已有的状态推未知的 
        for(int i=0;i<s.size();i++){
            for(int j=0;j<=i;j++){
                if(s[i]==s[j])
                    dp[j][i]=j+1<i?dp[j+1][i-1]:true;
                ans+=dp[j][i];
            }
        }
        return ans;
    }
};